public class MyHashMap<K, V> {
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 哈希表数组（链表法解决冲突）
    private Node<K, V>[] table;
    // 当前元素数量
    private int size;
    // 负载因子
    private final float loadFactor;

    // 构造函数
    public MyHashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int capacity, float loadFactor) {
        this.table = new Node[capacity];
        this.loadFactor = loadFactor;
        this.size = 0;
    }

    //------------------ 核心方法 ------------------//
    public void put(K key, V value) {
        if (key == null) return; // 简化处理，暂不支持null键
        int hash = hash(key);
        int index = hash & (table.length - 1); // 取模运算（要求容量是2的幂）

        // 遍历链表，检查key是否已存在
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                node.value = value; // 更新值
                return;
            }
            node = node.next;
        }

        // 新增节点（头插法）
        Node<K, V> newNode = new Node<>(hash, key, value, table[index]);
        table[index] = newNode;
        size++;

        // 扩容检查
        if (size > table.length * loadFactor) {
            resize();
        }
    }

    public V get(K key) {
        if (key == null) return null;
        int hash = hash(key);
        int index = hash & (table.length - 1);

        Node<K, V> node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null; // 未找到
    }

    //------------------ 关键内部方法 ------------------//
    private void resize() {
        int newCapacity = table.length * 2; // 扩容为原来的2倍
        Node<K, V>[] newTable = new Node[newCapacity];

        // 遍历旧表，重新散列所有节点
        for (Node<K, V> oldNode : table) {
            while (oldNode != null) {
                Node<K, V> next = oldNode.next;
                int newIndex = oldNode.hash & (newCapacity - 1); // 重新计算索引
                oldNode.next = newTable[newIndex]; // 头插法
                newTable[newIndex] = oldNode;
                oldNode = next;
            }
        }
        table = newTable; // 切换新表
    }

    // 哈希函数（简单调用Object的hashCode）
    private int hash(K key) {
        return key.hashCode();
    }

    //------------------ 内部节点类 ------------------//
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    //------------------ 测试代码 ------------------//
    public static void main(String[] args) {
        MyHashMap<String, Integer> map = new MyHashMap<>();
        map.put("A", 1);
        map.put("B", 2);
        map.put("C", 3);
        System.out.println(map.get("B")); // 输出: 2
        System.out.println(map.get("D")); // 输出: null
    }
}